/**
 * Created With IntelliJ IDEA
 * Description:牛客网：OR36 链表的回文结构
 * <a href="https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking">...</a>
 * User: DELL
 * Data: 2022-12-06
 * Time: 16:58
 */


import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
//第一步：寻找链表的中间结点
//第二步：逆序后半个链表
//第三步：逐个比对是否相等
//当第三步其中的一个链表走到末尾的时候，即证明原链表为回文结构
public class chkPalindrome {
    private ListNode reverseList (ListNode head) {
        ListNode newHead = new ListNode(0);  //头结点
        ListNode cur = head;
        ListNode nex = null;
        while (cur != null) {
            nex = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = nex;
        }
        return newHead.next;
    }
    public boolean chkPalindrome(ListNode A) {
        //判空处理
        if (A == null) {
            return false;
        }
        //第一步：寻找链表的中间结点
        ListNode fast = A;
        ListNode slow = A;
        //这里写成fast.next != null && fast.next.next != null是想让slow为中间结点的前序结点
        //然后将slow.next置为null，即可将原链表分为两个链表，之后逆序再进行后续操作。
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //将原链表拆分开
        fast = slow.next;
        slow.next = null;
        //第二步：逆序后半个链表
        fast = reverseList(fast);
        //第三步：逐个比对是否相等
        slow = A;
        while (slow != null && fast != null) {
            if (slow.val == fast.val) {
                slow = slow.next;
                fast = fast.next;
            } else {
                return false;
            }
        }
        return true;
    }
}